﻿
/*
* myVector.c
* 向量容器，动态数组
* 2012 - 8 - 22 westice
*/


#include "myVector.h"


myVector* createMyVector(int capacity){
	myVector* vector = (myVector*)malloc(sizeof(myVector));
	if(capacity < DEFAULT_MYVECTOR_CAPACITY)capacity = DEFAULT_MYVECTOR_CAPACITY;
	vector->maxCapacity = capacity;     //设置初始容量
	vector->vectorDataPtr = (myVectorNode*)malloc(sizeof(myVectorNode)*vector->maxCapacity);
	vector->length = 0;
	return vector;
}


void releaseMyVector(myVector* vec){
	//完全释放数组，必需是malloc的对象
	free(vec->vectorDataPtr);
	free(vec);
}

void myVectorAppendItem(myVector* vec,myVectorNode* item){
	int lastIndex_1 = myVectorLength(vec);
	myVectorInsertItemAt(vec,item,lastIndex_1);
}
void myVectorAppendVector(myVector* vec,myVector* vec1){
	//将vec1 接在 vec上
	//先计算连接之后的长度，如果容量够用，则直接复制进去即可
	//如果容量不够,则把vec的容量两个数组容量的总和
	int catLen = myVectorLength(vec) + myVectorLength(vec1);
	if(vec->maxCapacity < catLen){
		//扩展容量，长度暂时不变
		printf("myVector appendVector extend capacity\n");
		int newMaxCapacity = vec->maxCapacity + vec1->maxCapacity;
		myVector* newVec = createMyVector(newMaxCapacity);	
		newVec->length = myVectorLength(vec);
		
		//将vec的0~end 拷贝到 newVec的 0~end
		myRange oldRange = createMyRange(0,myVectorLength(vec));
		myVectorCopy(newVec,0,vec,oldRange);
		
		myVectorNode* oldVectorDataPtr = vec->vectorDataPtr;
		vec->maxCapacity = newMaxCapacity;     //设置容量
		vec->vectorDataPtr = newVec->vectorDataPtr;
		
		free(oldVectorDataPtr);   //释放旧的存储空间
	}
	int oldVecLength = myVectorLength(vec);
	vec->length = catLen;
	//连接vec1
	//将vec1的0~end拷贝到vec的 oldVecLength
	myRange vec1Range = createMyRange(0,myVectorLength(vec1));
	myVectorCopy(vec,oldVecLength,vec1,vec1Range);
}

void myVectorInsertItemAt(myVector* vec,myVectorNode* item,int index){
	//在index处插入一个元素，后面的后移
	//如果容量不够就要扩容
	if(index > myVectorLength(vec)){
		//索引出界,允许在最后面插入
		printf("myVector Insert index = %d outofRange = %d\n",index,myVectorLength(vec));
		return;
	}
	if(myVectorLength(vec) + 1 > vec->maxCapacity){
		//容量已满，扩容
		printf("myVector extend capacity\n");
		int newMaxCapacity = vec->maxCapacity * 2;
		myVector* newVec = createMyVector(newMaxCapacity);	
		newVec->length = myVectorLength(vec) + 1;
		myVectorNode* oldVectorDataPtr = vec->vectorDataPtr;
		
		//将vec的 0~index-1 拷贝到  newVec的0~index-1 
		myRange oldRange = createMyRange(0,index);
		myVectorCopy(newVec,0,vec,oldRange);
	
		//将vec的 index~end 拷贝到 newVec的 index+1 ~ end+1
		oldRange = createMyRange(index,myVectorLength(vec) - index);
		myVectorCopy(newVec,index+1,vec,oldRange);
		
		myVectorReplaceItemAt(newVec,item,index);
		vec->maxCapacity = newMaxCapacity;     //设置容量
		vec->vectorDataPtr = newVec->vectorDataPtr;
		vec->length = newVec->length;
		free(oldVectorDataPtr);   //释放旧的存储空间
		
	}else{	
		//先把index后面(包括index)的后移，只有一个数组
		//如果index 太靠前则使用重叠拷贝提高效率
		
		myRange oldRange = createMyRange(index,myVectorLength(vec) - index);
		int lastIndex = myVectorLength(vec) - 1;
		
		vec->length++;

		if(index/(float)myVectorLength(vec) < 0.8){
			myVectorCopyHasOverLap(vec,index + 1,vec,oldRange);
			//myVectorCopy(vec,index + 1,vec,oldRange);
		}else{
			for(; lastIndex >= index ;lastIndex--){
				myVectorNode* left = myVectorAt(vec,lastIndex); 
				myVectorReplaceItemAt(vec,left,lastIndex + 1);
			}
		}
		myVectorReplaceItemAt(vec,item,index);
	}
}

void myVectorReplaceItemAt(myVector* vec,myVectorNode* item,int index){
	if(index >= myVectorLength(vec)){
		//索引出界
		printf("myVector Replace index = %d outofRange = %d\n",index,myVectorLength(vec));
		return;
	}
	
	//替换index上的元素
	myVectorNode* prevPtr = myVectorAt(vec,index);
	prevPtr->bindDataPtr = item->bindDataPtr;  
	prevPtr->testValue = item->testValue;
}

void myVectorSwap(myVector* vec,int index,int index1){
	MYASSERT(index != index1);
	int largeIndex = LARGENUM(index,index1);
	if(largeIndex >= myVectorLength(vec)){
		//索引出界
		printf("myVector Swap index = %d outofRange = %d\n",index,myVectorLength(vec));
		return;
	}
	myVectorNode* node = myVectorAt(vec,index);
	myVectorNode* node1 = myVectorAt(vec,index1);
	int testValueBuff = node->testValue;
	int bindDataPtrBuff = node->bindDataPtr;
	node->testValue = node1->testValue;
	node->bindDataPtr = node1->bindDataPtr;
	node1->testValue = testValueBuff;
	node1->bindDataPtr = bindDataPtrBuff;
}

void myVectorRemoveItemAt(myVector* vec,int index){
	//删除index处的元素，后面的往前移一位，容量不变
	if(index >= myVectorLength(vec)){
		//索引出界
		printf("myVector remove index = %d outofRange = %d\n",index,myVectorLength(vec));
		return NULL;
	}
	
	int i = index + 1;
	for(;i < myVectorLength(vec);i++){
		myVectorNode* rightNode = myVectorAt(vec,i);
		myVectorReplaceItemAt(vec,rightNode,i - 1);
	}
	vec->length--;
}
void myVectorRemoveAll(myVector* vec){
	//清除所有的，如果容量大于默认容量，则把容量设为默认容量，以节省空间
	MYASSERT(vec->maxCapacity >= DEFAULT_MYVECTOR_CAPACITY);
	if(vec->maxCapacity > DEFAULT_MYVECTOR_CAPACITY){
		free(vec->vectorDataPtr);
		vec->maxCapacity = DEFAULT_MYVECTOR_CAPACITY;
		myVector* newVec = createMyVector(vec->maxCapacity);
		vec->vectorDataPtr = newVec->vectorDataPtr;
	}
	vec->length = 0;
}

void myVectorCopy(myVector* vec,int pos,myVector* vec1,myRange range1){
	//
	if((pos + range1.length) > myVectorLength(vec)){
		printf("myVectorCopy vec index out of Range:%d\n",myVectorLength(vec));
	}
	
	//这里可以优化为内存拷贝memcpy();
	/*
	int vecPos = pos;
	int i = 0;
	for(i = range1.pos;i < range1.pos + range1.length;i++){
		myVectorNode* node = myVectorAt(vec1,i);
		myVectorReplaceItemAt(vec,node,vecPos);
		vecPos++;
	}
	*/
	///*  //块拷贝，速度快！
	myVectorNode* srcPtr = vec1->vectorDataPtr + range1.pos;
	myVectorNode* destPtr = vec->vectorDataPtr + pos;
	memcpy(destPtr,srcPtr,range1.length*sizeof(myVectorNode));
	//*/
}

//vec1 拷贝到 vec的 pos ,但是有重叠，
//先把vec1的区域保存下来
void myVectorCopyHasOverLap(myVector* vec,int pos,myVector* vec1,myRange range1){
	if((pos + range1.length) > myVectorLength(vec)){
		printf("myVectorCopyHasOverLap vec index out of Range:%d\n",myVectorLength(vec));
	}
	myVectorNode* srcPtr = vec1->vectorDataPtr + range1.pos;
	myVectorNode* destPtr = vec->vectorDataPtr + pos;
	myVectorNode* vec1BuffPtr = (myVectorNode*)malloc(sizeof(myVectorNode)*range1.length);
	memcpy(vec1BuffPtr,srcPtr,range1.length*sizeof(myVectorNode));
	memcpy(destPtr,vec1BuffPtr,range1.length*sizeof(myVectorNode));
	free(vec1BuffPtr);
}


myVectorNode* myVectorAt(myVector* vec,int index){
	//返回index处的指针
	if(index >= myVectorLength(vec)){
		//索引出界
		printf("myVector At index = %d outofRange = %d\n",index,myVectorLength(vec));
		return NULL;
	}
	
	return (vec->vectorDataPtr + index);
}
int myVectorLength(myVector* vec){
	return vec->length;
}

void* myVectorBindDataAt(myVector* vec,int index){
	return myVectorAt(vec,index)->bindDataPtr;
}

void myVectorPrintAt(myVector* vec,int index){
	myVectorNode* item = myVectorAt(vec,index);
	if(item != NULL){
		printf("i:%d  testValue = %d  bindDataPtr = %x\n",index,item->testValue,item->bindDataPtr);
	}
}

void myVectorTestPrint(myVector* vec){
	int vecLength = myVectorLength(vec);
	printf("myVector info:   length = %d   maxCapacity = %d\n",vecLength,vec->maxCapacity);
	int i = 0;
	for(i = 0;i < vecLength ; i++){
		myVectorPrintAt(vec,i);
	}
	
}


